//----------------------------------------------------------
inline int bc(Int msk) {
        int c=0;
        for(c=0; msk ; ++c){
                msk&= (msk-1);
        }
        return c;
}

inline int encodePos(int rpos, int cpos, int RR, int CC){
	return rpos*CC + cpos ;
}
inline int decodeR(int rpos, int RR, int CC){
	return rpos/CC;
}
inline int decodeC(int cpos, int RR, int CC){
	return cpos%CC;
}
//----------------------------------------------------------
inline bool int_overflow(int a , int b, string com){
    long long max_value = (1LL<<31)-1;
    if(com=="add"){
        return ( a > (max_value-b) ) ;
    }
    else{
        assert(b!=0);
        return ( a > (max_value/b) );
    }
}
inline bool long_overflow(long long a , long long b, string com){
    unsigned long long max_value = (1ULL<<63)-1;
    if(com=="plus"){
        return ( a > (max_value-b) ) ;
    }
    else{
        assert(b!=0);
        return ( a > (max_value/b) );
    }
}
//check if a number is exact power of 2
inline bool pTwo(unsigned long long x) {
    return (x != 0) && ((x & (x - 1)) == 0);
}

template< class T >
inline T two( T var ){
    return var*var ;
}
inline Int fastPow(Int x, Int y) {
    Int res= (Int)1;
    for ( ; y ; ) {
        if ( (y&1) ) {
            res*= x;
        }
        x*=x;
        y>>=1;
    }
    return res;
}
//fast power with mod
const Int mod = 1000000007LL;
inline Int domod(Int x){
  if(x<0)x+=mod;
  return x%mod;
}
inline Int fastPow(Int a, Int b) {
    Int x= (Int)1,y= domod(a);

    while (b>0) {
        if (b&1) {
            x= domod(x*y);
        }
        y=domod(y*y);
        b>>=1;
    }
    return domod(x);
}

template< class T1, class T2 >
inline T2 MOD( T1 x , T2 b ){
    return (x%b);
}
template< class T >
inline T gcd(T a, T b){
    // NEGATIVE VALUE'R GCD HOTE PARBE NA
    assert( (a >=0 && b>=0 ) );
    while( b > T(0) ){
        a%=b;
        swap(a,b);
    }
return a;
}

inline int toI(string _str){
    // STRING EMPTY HOTE PARBE NA
    assert( LN(_str) );
    int var;
    sscanf(_str.c_str(),"%d",&var);
return var;
}
inline string toS(int var){
    char _buff[50];
    sprintf( _buff,"%d",var);
return (string)_buff;
}


struct Triple {
    Int d;
    Int x;
    Int y;
    Triple(Int d, Int x, Int y):
            d(d),x(x),y(y) {
        ;
    }
};
Triple egcd(Int a, Int b) {
    if (!b)return Triple(a,1,0);
    Triple q=egcd(b,a%b);
    return Triple(q.d, q.y, q.x-a/b*q.y);
}
inline Int invmod(Int a, Int n) {
    Triple t=egcd(a,n);
    if (t.d>1)return 0;
    Int r=t.x%n;
    return (r<0?r+n:r);
}
const int mod=(int)1e9+7;
const int maxn=1010;
Int im[maxn]; //inverse mod
Int fact[maxn];
inline void findFactorials(int upto) {
    fact[0]=fact[1]=im[1]=1;
    for (int i=2;i<=upto;++i) {
        im[i]=invmod(i,mod);
        fact[i]=(fact[i-1]*i)%mod;
    }
}
Int C[maxn][maxn];
// find NcR
Int ncr(Int a, Int b) {
    int LM=min(b,a-b);
    if (C[a][LM])return C[a][LM];
    C[a][0]=1LL;
    int LIM=(a+3)>>1;
    for (int U=a,D=1; D<LIM; ++D,--U) {
        C[a][D]=(((C[a][D-1] * U)%mod) * im[D])% mod;
    }
    return C[a][LM];
}
// another NcR formula
Int ncr(Int n, Int r){
    return (fact[n]*invmod(fact[r],mod)*invmod(fact[n-r],mod))%mod;
}

inline void preprocess() {
    findFactorials(1000);
    SET(C,0);
}

Int fib[maxn+5];
inline void Fibonacci(int upto) {
    fib[0]=0;
    fib[1]=1;
    fib[2]=1;
    for (int i=3;i<=upto;++i) {
        fib[i]=fib[i-1]+fib[i-2];
    }
}

/*
 * http://goo.gl/8tUaQ
 * Zeckendorf(n)= {
 * local(k); a=0;
 * while(n>0, k=0;
 * 	while(fibonacci(k)<=n, k=k+1);
 * 	a=a+10^(k-3); n=n-fibonacci(k-1); ); a
 * }
 *
 * { for (n=0, 10000, Zeckendorf(n); print(n, " ", a);
 */

int res[50];
int leftmost;
inline void Zeckendorf(int n) {
    int k;
    SET(res,0);

    leftmost=-1;
    while (n>0) {
        k=0;
        while (fib[k]<=n) {
            k=k+1;
        }
        res[k-3]=1;
        n=n-fib[k-1];
        if (leftmost==-1)leftmost=k-3;
    }
    for (int i=leftmost;i>=0;--i)
        putchar(res[i]?'1':'0');
    line;

}
int tot;
vector< pair<Int,int> > primeDivisors;
inline void factorize(Int number) {
    primeDivisors.clear();
    for (int i=0; i<cnt&&primes[i]*primes[i]<=number;++i) {
        if ( (number%primes[i]) ==0) {
            int power=0;
            while ((number%primes[i])==0) {
                number/=primes[i];
                ++power;
            }
            primeDivisors.pb(mk(primes[i],power));
        }
    }
    if ( number!=1) {
        primeDivisors.pb(mk(number,1));
    }
    tot=SZ(primeDivisors);
}

vector< pair<Int,int> >primeDivisors;
inline void factorize(Int number) {
    primeDivisors.clear();
    for (Int i = 2; i * i <= number; i++) {
        if (number % i == 0) {
            int power = 0;
            do {
                power++;
                number /= i;
            } while (number % i == 0);
            primeDivisors.pb(mk(i, power));
        }
    }
    if (number != 1)
        primeDivisors.pb(mk(number, 1));
}
vector<int> divisors;
void genDivisor(int at, int current) {
    if (at==SZ(primeDivisors)) {
        divisors.pb(current);
        return ;
    }
    int p=primeDivisors[at].first;
    int power=primeDivisors[at].second;
    for (int i=0;i<=power;++i) {
        genDivisor(at+1,current);
        current*=p;
    }
}
inline void getDivisor(int N) {
    factorize(N);
    divisors.clear();
    genDivisor(0,1);
    cout<<N<<" = ";
    fo(i,SZ(divisors)){
      cout<<divisors[i]<<' ';
    }
    line;
}

const int inf = (int)100000;
bitset<inf> used;
int primes[inf];
int cnt;

inline void sieve() {
    int sqrtN = (int)sqrt((double)inf)+1;
    used=0;
    int i,j;
    for (i=3;i<=sqrtN;i+=2) {
        if (!used[i]) {
            for (j=i*i;j<inf;j+=i) {
                used[j]=1;
            }
        }
    }
    cnt=0;
    primes[cnt++]=2;
    for (i=3;i<inf;i+=2) {
        if (!used[i])primes[cnt++]=i;
    }
}
inline Int getNext(int num, int prime) {
    Int v=ceil( ((double)num)/prime );
    v=v*prime;
    if (v==prime)v+=prime;
    return v;
}
inline void segmentSieve(int a, int b) {
    used=0;
    int i;
    int upto= (int)sqrt(double(b))+1;
    for (i=0; i<cnt&&primes[i]<=upto;++i) {
        for (Int j=getNext(a,primes[i]);j<=b;j+=primes[i]) {
            used[j-a]=1;
        }
    }
    int cnt=0;
    for (Int i=lo;i<=hi;++i) {
        if (i!=1&&!used[ (int)i-lo]) {
            ++cnt;
        }
    }
    cout<<cnt;
}
//-------------------------------------------------------------------
// return number of divisors of a number "num"
// need sieve() function to call first

inline Int Divisors(Int num) {
    Int res=1;
    for (Int i=0; i<cnt&&(primes[i]*primes[i])<=num; ++i) {
        if ( num%primes[i] ==0 ) {
            int power=0;
            do {
                num/=primes[i];
                ++power;
            } while (num%primes[i] ==0 );
            res*=(power+1);
        }
    }
    if (num!=1) {
        res*=(2);
    }
    return res;
}
// return number of divisors of a number "num^3"
inline Int Divisors_3(Int num) {
    Int res=1;
    for (Int i=2; i*i<=num; ++i) {
        if ( (num%i) ==0 ) {
            int power=0;
            do {
                num/=i;
                ++power;
            } while (num%i ==0 );
            res*=  ( (power*3) +1 )  ;
        }
    }
    if (num!=1) {
        res*=( 4 ) ;
    }
    return res;
}
//-----------------------------------------------------------

// number of tailing zero = min( number of 2, number of 5 )
//----------------------------------------------
//calculate
//number of 2, and 5  n!
inline Int calc(int n,int x) {
    Int ret=0;
    for ( Int i=1; i<=n; i*=x ) {
        Int var = (Int)(n/i);
        if (var<0)break;
        ret+=var;
    }
    return ret;
}

//calculate
//number of 2, and 5 in p^q
inline Int calc(int p,int q, int x) {
    //factorize p respect to x;
    Int ret=0;

    while ( (p%x)==0 ) {
        p/=x;
        ++ret;
    }
    return ret*q;
}
//----------------------------------------------
  
const double gammaa = 0.5772156649;
const double Bn[] = {1.0/6.0, -1.0/30.0, 1.0/42.0, -1.0/30.0, 5.0/66.0};
//calculates n-th Harmonic number
//Hn = 1 + 1/2 + 1/3 + ..... + 1/n
inline double Hn(int n) {
    if (n <= 0) return 0;
    double r = 0;
    int i;
    if (n <= 1000) {
        for (i = 1; i <= n; i++) {
            r += (1.0/(double)i);
        }
        return r;
    }
    r = log(n) + gammaa + .5/n;
    for (i = 0; i < 5; i++) {
        r -= (Bn[i] / (2.0*(i+1)*pow(n,2*(i+1)))) ;
    }
    return r;
}

//how many number divisible in range given yeara <= yearb
public long Calculate(long yeara, long yearb, int div) {
        long a = (long) Math.ceil(((double) yeara) / div) * div;
        long b = (long) Math.floor(((double) yearb) / div) * div;
        //debug(yeara+"_"+yearb+"_"+div);
        if (a > b) {
            return 0;
        }
        return ((b - a) / div) + 1;
}
//Infinite chessboard distance between 2 cells.
inline int shortest_path(int x1, int y1, int x2, int y2) {
    int dx=abs(x2-x1);
    int dy=abs(y2-y1);
    int lb=(dx+1)/2;
    lb=max(lb, (dy+1)/2);
    lb=max(lb, (dx+dy+2)/3 );
    while ((lb%2)!=(dx+dy)%2) lb++;
    if (abs(dx)==1 && dy==0) return 3;
    if (abs(dy)==1 && dx==0) return 3;
    if (abs(dx)==2 && abs(dy)==2) return 4;
    return lb;
}

//Task of Joseph
int joseph (int n, int k) {
	if (n == 1)  return 0;
	if (k == 1)  return n-1;
	if (k > n)  return (joseph (n-1, k) + k) % n;
	int cnt = n / k;
	int res = joseph (n - cnt, k);
	res -= n % k;
	if (res < 0)  res += n;
	else  res += res / (k - 1);
	return res;
}